#pragma once

#include "visited_list_pool.hpp"
#include "hnswlib.hpp"
#include <random>
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

template<typename T>
void writeBinaryPOD(std::ostream &out, const T &podRef) {
    out.write((char *) &podRef, sizeof(T));
}

template<typename T>
static void readBinaryPOD(std::istream &in, T &podRef) {
    in.read((char *) &podRef, sizeof(T));
}

#define DEBUG_LIB 1
namespace MIPSGraph {
    typedef unsigned int tableint;
    typedef unsigned int linklistsizeint;

    template<typename dist_t>
    class HierarchicalNSW : public AlgorithmInterface<dist_t> {
    public:
        HierarchicalNSW(SpaceInterface <dist_t> *s) {

        }

        HierarchicalNSW(SpaceInterface <dist_t> *s, const std::string &location, bool nmslib = false) {
            LoadIndex(location, s);
        }

        HierarchicalNSW(SpaceInterface <dist_t> *s, size_t maxElements, size_t M, size_t efConstruction, float alpha) :
                ll_locks(maxElements), elementLevels(maxElements) {
            maxelements_ = maxElements;

            data_size_ = s->get_data_size();
            fstdistfunc_ = s->get_dist_func();
            dist_func_param_ = s->get_dist_func_param();
            M_ = M;
            maxM_ = M_;
            maxM0_ = M_ * 2;
            efConstruction_ = efConstruction;
            ef_ = -1;
            report_every_ = 5000;
            alpha_ = alpha;


            size_links_level0_ = maxM0_ * sizeof(tableint) + sizeof(linklistsizeint);
            size_data_per_element_ = size_links_level0_ + data_size_ + sizeof(labeltype);
            offsetData_ = size_links_level0_;
            offset_label_ = size_links_level0_ + data_size_;
            offsetLevel0_ = 0;
            //cout << offsetData_ << "\t" << offset_label_ << "\n";
            //cout << size_links_level0_ << "\t" << data_size_ << "\t" << sizeof(labeltype) << "\n";

            data_level0_memory_ = (char *) malloc(maxelements_ * size_data_per_element_);

            cur_element_count = 0;

            visitedlistpool = new VisitedListPool(1, maxElements);



            //initializations for special treatment of the first node
            enterpoint_node = -1;
            maxlevel_ = -1;

            linkLists_ = (char **) malloc(sizeof(void *) * maxelements_);
            size_links_per_element_ = maxM_ * sizeof(tableint) + sizeof(linklistsizeint);
            mult_ = 1 / log(1.0 * M_);
            revSize_ = 1.0 / mult_;
        }

        ~HierarchicalNSW() {

            free(data_level0_memory_);
            for (tableint i = 0; i < cur_element_count; i++) {
                if (elementLevels[i] > 0)
                    free(linkLists_[i]);
            }
            free(linkLists_);
            delete visitedlistpool;
        }

        size_t maxelements_;
        size_t cur_element_count;
        size_t size_data_per_element_;
        size_t size_links_per_element_;

        size_t M_;
        size_t maxM_;
        size_t maxM0_;
        size_t efConstruction_;
        double mult_, revSize_;
        int maxlevel_;
        int report_every_;
        float alpha_;


        VisitedListPool *visitedlistpool;
        std::mutex cur_element_count_guard_;
        std::mutex MaxLevelGuard_;
        std::vector<std::mutex> ll_locks;
        tableint enterpoint_node;

        size_t dist_calc;
        size_t size_links_level0_;
        size_t offsetData_, offsetLevel0_;
        size_t offset_label_;


        char *data_level0_memory_;
        char **linkLists_;
        std::vector<float> elementNorms;
        std::vector<int> elementLevels;


        size_t data_size_;
        DISTFUNC <dist_t> fstdistfunc_;
        void *dist_func_param_;
        std::default_random_engine generator = std::default_random_engine(100);

        inline labeltype getExternalLabel(tableint internal_id) {
            return *((labeltype * )(data_level0_memory_ + internal_id * size_data_per_element_ + offset_label_));
        }

        inline labeltype *getExternalLabeLp(tableint internal_id) {
            return (labeltype * )(data_level0_memory_ + internal_id * size_data_per_element_ + offset_label_);
        }

        inline char *getDataByInternalId(tableint internal_id) {
            return (data_level0_memory_ + internal_id * size_data_per_element_ + offsetData_);
        }

        int getRandomLevel(double revSize) {
            std::uniform_real_distribution<double> distribution(0.0, 1.0);
            double r = -log(distribution(generator)) * revSize;
            return (int) r;
        }

        // use cosine as similarity
        std::priority_queue<std::pair<dist_t, tableint  >> searchBaseLayer(tableint ep, void *datapoint, int layer) {
            VisitedList *vl = visitedlistpool->getFreeVisitedList();
            vl_type *massVisited = vl->mass;
            vl_type currentV = vl->curV;

            std::priority_queue<std::pair<dist_t, tableint  >> topResults;
            std::priority_queue<std::pair<dist_t, tableint >> candidateSet;
            dist_t dist = fstdistfunc_(datapoint, getDataByInternalId(ep), dist_func_param_) / elementNorms[ep];

            topResults.emplace(dist, ep);
            candidateSet.emplace(-dist, ep);
            massVisited[ep] = currentV;
            dist_t lowerBound = dist;

            while (!candidateSet.empty()) {

                std::pair<dist_t, tableint> curr_el_pair = candidateSet.top();

                if ((-curr_el_pair.first) > lowerBound) {
                    break;
                }
                candidateSet.pop();

                tableint curNodeNum = curr_el_pair.second;

                std::unique_lock<std::mutex> lock(ll_locks[curNodeNum]);

                int *data;// = (int *)(linkList0_ + curNodeNum * size_links_per_element0_);
                if (layer == 0)
                    data = (int *) (data_level0_memory_ + curNodeNum * size_data_per_element_ + offsetLevel0_);
                else
                    data = (int *) (linkLists_[curNodeNum] + (layer - 1) * size_links_per_element_);
                int size = *data;
                tableint *datal = (tableint *) (data + 1);
                _mm_prefetch((char *) (massVisited + *(data + 1)), _MM_HINT_T0);
                _mm_prefetch((char *) (massVisited + *(data + 1) + 64), _MM_HINT_T0);
                _mm_prefetch(getDataByInternalId(*datal), _MM_HINT_T0);
                _mm_prefetch(getDataByInternalId(*(datal + 1)), _MM_HINT_T0);

                for (int j = 0; j < size; j++) {
                    tableint tnum = *(datal + j);
                    _mm_prefetch((char *) (massVisited + *(datal + j + 1)), _MM_HINT_T0);
                    _mm_prefetch(getDataByInternalId(*(datal + j + 1)), _MM_HINT_T0);
                    if (massVisited[tnum] != currentV) {
                        massVisited[tnum] = currentV;
                        char *currObj1 = (getDataByInternalId(tnum));

                        dist_t dist = fstdistfunc_(datapoint, currObj1, dist_func_param_) / elementNorms[tnum];
                        if (topResults.top().first > dist || topResults.size() < efConstruction_) {
                            candidateSet.emplace(-dist, tnum);
                            _mm_prefetch(getDataByInternalId(candidateSet.top().second), _MM_HINT_T0);
                            topResults.emplace(dist, tnum);
                            if (topResults.size() > efConstruction_) {
                                topResults.pop();
                            }
                            lowerBound = topResults.top().first;
                        }
                    }
                }
            }
            visitedlistpool->releaseVisitedList(vl);

            return topResults;
        }

        struct CompareByFirst {
            constexpr bool
            operator()(std::pair<dist_t, tableint> const &a, std::pair<dist_t, tableint> const &b) const noexcept {
                return a.first < b.first;
            }
        };

        void
        getNeighborsByHeuristic2(std::priority_queue<std::pair<dist_t, tableint>> &topResults, const int Mcurrent) {
            if (topResults.size() < Mcurrent) {
                return;
            }
            std::priority_queue<std::pair<dist_t, tableint>> resultSet;
            /*
             * evaluation is maximum inner product
             * topResults is min heap
             * resultSet is max heap
             */
            std::vector<std::pair<dist_t, tableint>> returnlist;
            while (topResults.size() > 0) {
                resultSet.emplace(-topResults.top().first, topResults.top().second);
                topResults.pop();
            }

            while (resultSet.size()) {
                if (returnlist.size() >= Mcurrent)
                    break;
                std::pair<dist_t, tableint> curen = resultSet.top();
                dist_t dist_to_query = -curen.first;
                resultSet.pop();
                bool good = true;
                for (std::pair<dist_t, tableint> curen2 : returnlist) {
                    dist_t curdist =
                            fstdistfunc_(getDataByInternalId(curen2.second), getDataByInternalId(curen.second),
                                         dist_func_param_);
                    if (curdist < alpha_ * dist_to_query) {
                        good = false;
                        break;
                    }
                }
                if (good) {
                    returnlist.push_back(curen);
                }


            }

            for (std::pair<dist_t, tableint> curen2 : returnlist) {
                topResults.emplace(-curen2.first, curen2.second);
            }
        }

        linklistsizeint *get_linklist0(tableint cur_c) {
            return (linklistsizeint *) (data_level0_memory_ + cur_c * size_data_per_element_ + offsetLevel0_);
        };

        linklistsizeint *get_linklist(tableint cur_c, int level) {
            return (linklistsizeint *) (linkLists_[cur_c] + (level - 1) * size_links_per_element_);
        };

        //use mips to connect
        void mutuallyConnectNewElement(void *datapoint, tableint cur_c
                                       , std::priority_queue<std::pair<dist_t, tableint  >> topResults, int level) {

            size_t Mcurmax = level ? maxM_ : maxM0_;
            getNeighborsByHeuristic2(topResults, M_);
            while (topResults.size() > M_) {
                throw std::exception();
            }
            std::vector<tableint> rez;
            rez.reserve(M_);
            while (topResults.size() > 0) {
                rez.push_back(topResults.top().second);
                topResults.pop();
            }
            {
                linklistsizeint *ll_cur;
                if (level == 0)
                    ll_cur = (linklistsizeint *) (data_level0_memory_ + cur_c * size_data_per_element_ + offsetLevel0_);
                else
                    ll_cur = (linklistsizeint *) (linkLists_[cur_c] + (level - 1) * size_links_per_element_);
                if (*ll_cur) {
                    std::cout << *ll_cur << "\n";
                    std::cout << elementLevels[cur_c] << "\n";
                    std::cout << level << "\n";
                    throw std::runtime_error("Should be blank");
                }
                *ll_cur = rez.size();
                tableint *data = (tableint *) (ll_cur + 1);


                for (int idx = 0; idx < rez.size(); idx++) {
                    if (data[idx])
                        throw std::runtime_error("Should be blank");
                    if (level > elementLevels[rez[idx]])
                        throw std::runtime_error("Bad level");

                    data[idx] = rez[idx];
                }
            }
            for (int idx = 0; idx < rez.size(); idx++) {

                std::unique_lock<std::mutex> lock(ll_locks[rez[idx]]);

                if (rez[idx] == cur_c)
                    throw std::runtime_error("Connection to the same element");
                linklistsizeint *ll_other;
                if (level == 0)
                    ll_other = (linklistsizeint *) (data_level0_memory_ + rez[idx] * size_data_per_element_ +
                                                    offsetLevel0_);
                else
                    ll_other = (linklistsizeint *) (linkLists_[rez[idx]] + (level - 1) * size_links_per_element_);
                if (level > elementLevels[rez[idx]])
                    throw std::runtime_error("Bad level");
                int sz_link_list_other = *ll_other;

                if (sz_link_list_other > Mcurmax || sz_link_list_other < 0)
                    throw std::runtime_error("Bad sz_link_list_other");

                if (sz_link_list_other < Mcurmax) {
                    tableint *data = (tableint *) (ll_other + 1);
                    data[sz_link_list_other] = cur_c;
                    *ll_other = sz_link_list_other + 1;
                } else {
                    // finding the "weakest" element to replace it with the new one
                    tableint *data = (tableint *) (ll_other + 1);
                    dist_t d_max = fstdistfunc_(getDataByInternalId(cur_c), getDataByInternalId(rez[idx]),
                                                dist_func_param_);
                    // Heuristic:
                    std::priority_queue<std::pair<dist_t, tableint>> candidates;
                    candidates.emplace(d_max, cur_c);

                    for (int j = 0; j < sz_link_list_other; j++) {
                        candidates.emplace(fstdistfunc_(getDataByInternalId(data[j]), getDataByInternalId(rez[idx]),
                                                        dist_func_param_), data[j]);
                    }

                    getNeighborsByHeuristic2(candidates, Mcurmax);

                    int indx = 0;
                    while (candidates.size() > 0) {
                        data[indx] = candidates.top().second;
                        candidates.pop();
                        indx++;
                    }
                    *ll_other = indx;
                    // Nearest K:
                    /*int indx = -1;
                    for (int j = 0; j < sz_link_list_other; j++) {
                        dist_t d = fstdistfunc_(getDataByInternalId(data[j]), getDataByInternalId(rez[idx]), dist_func_param_);
                        if (d > d_max) {
                            indx = j;
                            d_max = d;
                        }
                    }
                    if (indx >= 0) {
                        data[indx] = cur_c;
                    } */
                }

            }
        }

        std::mutex global;
        size_t ef_;

        void setEf(size_t ef) {
            ef_ = ef;
        }

        void addPoint(void *datapoint, labeltype label, int level = -1) {

            tableint cur_c = 0;
            {
                std::unique_lock<std::mutex> lock(cur_element_count_guard_);
                if (cur_element_count >= maxelements_) {
                    std::cout << "The number of elements exceeds the specified limit\n";
                    throw std::runtime_error("The number of elements exceeds the specified limit");
                };
                cur_c = cur_element_count;
                cur_element_count++;
                if (cur_element_count % report_every_ == 0) {
                    printf("add point %d\n", cur_element_count);
                }
            }
            std::unique_lock<std::mutex> lock_el(ll_locks[cur_c]);
            int curlevel = getRandomLevel(mult_);
            if (level > 0)
                curlevel = level;
            elementLevels[cur_c] = curlevel;


            std::unique_lock<std::mutex> templock(global);
            int maxlevelcopy = maxlevel_;
            if (curlevel <= maxlevelcopy)
                templock.unlock();
            tableint currObj = enterpoint_node;


            memset(data_level0_memory_ + cur_c * size_data_per_element_ + offsetLevel0_, 0, size_data_per_element_);
            // Initialisation of the data and label
            memcpy(getExternalLabeLp(cur_c), &label, sizeof(labeltype));
            memcpy(getDataByInternalId(cur_c), datapoint, data_size_);


            if (curlevel) {
                linkLists_[cur_c] = (char *) malloc(size_links_per_element_ * curlevel);
                memset(linkLists_[cur_c], 0, size_links_per_element_ * curlevel);
            }
            if (currObj != -1) {

                //当随机出来的点层数小于最大层数, 就从上到下搜索
                if (curlevel < maxlevelcopy) {

                    dist_t curdist = fstdistfunc_(datapoint, getDataByInternalId(currObj), dist_func_param_) /
                                     elementNorms[currObj];
                    for (int level = maxlevelcopy; level > curlevel; level--) {

                        bool changed = true;
                        while (changed) {
                            changed = false;
                            linklistsizeint *data;
                            std::unique_lock<std::mutex> lock(ll_locks[currObj]);
                            data = (linklistsizeint *) (linkLists_[currObj] + (level - 1) * size_links_per_element_);
                            int size = *data;
                            tableint *datal = (tableint *) (data + 1);
                            for (int i = 0; i < size; i++) {
                                tableint cand = datal[i];
                                if (cand < 0 || cand > maxelements_)
                                    throw std::runtime_error("cand error");
                                dist_t d = fstdistfunc_(datapoint, getDataByInternalId(cand), dist_func_param_) /
                                           elementNorms[cand];
                                if (d < curdist) {
                                    curdist = d;
                                    currObj = cand;
                                    changed = true;
                                }
                            }
                        }
                    }
                }

                for (int level = std::min(curlevel, maxlevelcopy); level >= 0; level--) {
                    if (level > maxlevelcopy || level < 0)
                        throw std::runtime_error("Level error");

                    std::priority_queue<std::pair<dist_t, tableint  >> topResults = searchBaseLayer(currObj, datapoint,
                                                                                                    level);
                    std::priority_queue<std::pair<dist_t, tableint >> topResultsMIPS;
                    while (!topResults.empty()) {
                        std::pair<dist_t, tableint> tmp_pair = topResults.top();
                        topResults.pop();
                        tmp_pair.first *= elementNorms[tmp_pair.second];
                        topResultsMIPS.emplace(tmp_pair);
                    }
                    mutuallyConnectNewElement(datapoint, cur_c, topResultsMIPS, level);
                }

            } else {
                // Do nothing for the first element
                enterpoint_node = 0;
                maxlevel_ = curlevel;
            }

            //Releasing lock for the maximum level
            if (curlevel > maxlevelcopy) {
                enterpoint_node = cur_c;
                maxlevel_ = curlevel;
            }
        };

        //先搜索cosine, 然后再根据mips搜索
        std::priority_queue<std::pair<dist_t, labeltype >> searchKnn(void *query_data, int k) {
            tableint currObj = enterpoint_node;
            dist_t curdist = fstdistfunc_(query_data, getDataByInternalId(enterpoint_node), dist_func_param_) /
                             elementNorms[enterpoint_node];
            dist_calc++;
            for (int level = maxlevel_; level > 0; level--) {
                bool changed = true;
                while (changed) {
                    changed = false;
                    int *data = (int *) (linkLists_[currObj] + (level - 1) * size_links_per_element_);
                    int size = *data;
                    tableint *datal = (tableint *) (data + 1);
                    for (int i = 0; i < size; i++) {
                        tableint cand = datal[i];
                        if (cand < 0 || cand > maxelements_)
                            throw std::runtime_error("cand error");
                        dist_t d = fstdistfunc_(query_data, getDataByInternalId(cand), dist_func_param_) /
                                   elementNorms[cand];
                        dist_calc++;
                        if (d < curdist) {
                            curdist = d;
                            currObj = cand;
                            changed = true;
                        }
                    }
                }
            }

            //先根据cosine进行搜索
            std::priority_queue<std::pair<dist_t, tableint>, std::vector<std::pair<dist_t, tableint>>,
                    CompareByFirst> topResults = searchBaseLayerST(currObj, query_data, ef_);
            //将topResults转换成vector
            std::vector<std::pair<dist_t, tableint>> candidate_cosine;
            while (!topResults.empty()) {
                std::pair<dist_t, tableint> tmp_candidate = topResults.top();
                topResults.pop();
                tmp_candidate.first *= elementNorms[tmp_candidate.second];
//                dist_calc++;
                candidate_cosine.push_back(tmp_candidate);
            }
            //将cosine搜索后的结果放到mips中进行搜索
            topResults = searchBaseLayerMIPS(candidate_cosine, query_data, ef_);

            std::priority_queue<std::pair<dist_t, labeltype >> results;
            while (topResults.size() > k) {
                topResults.pop();
            }
            while (topResults.size() > 0) {
                std::pair<dist_t, tableint> rez = topResults.top();
                results.push(std::pair<dist_t, labeltype>(rez.first, getExternalLabel(rez.second)));
                topResults.pop();
            }
            return results;
        };

        std::priority_queue<std::pair<dist_t, tableint>, std::vector<std::pair<dist_t, tableint>>, CompareByFirst>
        searchBaseLayerMIPS(
                std::vector<std::pair<dist_t, tableint>> &enterPoint_l
                , void *datapoint, size_t ef) {
            VisitedList *vl = visitedlistpool->getFreeVisitedList();
            vl_type *massVisited = vl->mass;
            vl_type currentV = vl->curV;

            std::priority_queue<std::pair<dist_t, tableint>, std::vector<std::pair<dist_t, tableint>>, CompareByFirst>
                    topResults;
            std::priority_queue<std::pair<dist_t, tableint>, std::vector<std::pair<dist_t, tableint>>, CompareByFirst>
                    candidateSet;
            int ep_size = enterPoint_l.size();
            dist_t lowerBound = 0;
            {
                std::pair<dist_t, tableint> tmp_ep_pair = enterPoint_l[0];
                topResults.emplace(tmp_ep_pair.first, tmp_ep_pair.second);
                candidateSet.emplace(-tmp_ep_pair.first, tmp_ep_pair.second);
                massVisited[tmp_ep_pair.second] = currentV;
                lowerBound = tmp_ep_pair.first;
            }
            for (int i = 1; i < ep_size; i++) {
                std::pair<dist_t, tableint> tmp_ep_pair = enterPoint_l[i];
                topResults.emplace(tmp_ep_pair.first, tmp_ep_pair.second);
                candidateSet.emplace(-tmp_ep_pair.first, tmp_ep_pair.second);
                massVisited[tmp_ep_pair.second] = currentV;
                lowerBound = std::min(lowerBound, tmp_ep_pair.first);
            }

            while (!candidateSet.empty()) {

                std::pair<dist_t, tableint> curr_el_pair = candidateSet.top();

                if ((-curr_el_pair.first) > lowerBound) {
                    break;
                }
                candidateSet.pop();

                tableint curNodeNum = curr_el_pair.second;
                int *data = (int *) (data_level0_memory_ + curNodeNum * size_data_per_element_ + offsetLevel0_);
                int size = *data;
                _mm_prefetch((char *) (massVisited + *(data + 1)), _MM_HINT_T0);
                _mm_prefetch((char *) (massVisited + *(data + 1) + 64), _MM_HINT_T0);
                _mm_prefetch(data_level0_memory_ + (*(data + 1)) * size_data_per_element_ + offsetData_, _MM_HINT_T0);
                _mm_prefetch((char *) (data + 2), _MM_HINT_T0);

                for (int j = 1; j <= size; j++) {
                    int tnum = *(data + j);
                    _mm_prefetch((char *) (massVisited + *(data + j + 1)), _MM_HINT_T0);
                    _mm_prefetch(data_level0_memory_ + (*(data + j + 1)) * size_data_per_element_ + offsetData_,
                                 _MM_HINT_T0);////////////
                    if (massVisited[tnum] != currentV) {

                        massVisited[tnum] = currentV;

                        char *currObj1 = (getDataByInternalId(tnum));
                        dist_t dist = fstdistfunc_(datapoint, currObj1, dist_func_param_);
                        dist_calc++;
                        if (topResults.top().first > dist || topResults.size() < ef) {
                            candidateSet.emplace(-dist, tnum);
                            _mm_prefetch(data_level0_memory_ + candidateSet.top().second * size_data_per_element_ +
                                         offsetLevel0_,///////////
                                         _MM_HINT_T0);////////////////////////

                            topResults.emplace(dist, tnum);

                            if (topResults.size() > ef) {
                                topResults.pop();
                            }
                            lowerBound = topResults.top().first;
                        }
                    }
                }
            }

            visitedlistpool->releaseVisitedList(vl);
            return topResults;
        }

        //根据cosine在最底层进行搜索
        std::priority_queue<std::pair<dist_t, tableint>, std::vector<std::pair<dist_t, tableint>>, CompareByFirst>
        searchBaseLayerST(tableint ep, void *datapoint, size_t ef) {
            VisitedList *vl = visitedlistpool->getFreeVisitedList();
            vl_type *massVisited = vl->mass;
            vl_type currentV = vl->curV;

            std::priority_queue<std::pair<dist_t, tableint>, std::vector<std::pair<dist_t, tableint>>, CompareByFirst>
                    topResults;
            std::priority_queue<std::pair<dist_t, tableint>, std::vector<std::pair<dist_t, tableint>>, CompareByFirst>
                    candidateSet;
            dist_t dist = fstdistfunc_(datapoint, getDataByInternalId(ep), dist_func_param_) / elementNorms[ep];
            dist_calc++;
            topResults.emplace(dist, ep);
            candidateSet.emplace(-dist, ep);
            massVisited[ep] = currentV;
            dist_t lowerBound = dist;

            while (!candidateSet.empty()) {

                std::pair<dist_t, tableint> curr_el_pair = candidateSet.top();

                if ((-curr_el_pair.first) > lowerBound) {
                    break;
                }
                candidateSet.pop();

                tableint curNodeNum = curr_el_pair.second;
                int *data = (int *) (data_level0_memory_ + curNodeNum * size_data_per_element_ + offsetLevel0_);
                int size = *data;
                _mm_prefetch((char *) (massVisited + *(data + 1)), _MM_HINT_T0);
                _mm_prefetch((char *) (massVisited + *(data + 1) + 64), _MM_HINT_T0);
                _mm_prefetch(data_level0_memory_ + (*(data + 1)) * size_data_per_element_ + offsetData_, _MM_HINT_T0);
                _mm_prefetch((char *) (data + 2), _MM_HINT_T0);

                for (int j = 1; j <= size; j++) {
                    int tnum = *(data + j);
                    _mm_prefetch((char *) (massVisited + *(data + j + 1)), _MM_HINT_T0);
                    _mm_prefetch(data_level0_memory_ + (*(data + j + 1)) * size_data_per_element_ + offsetData_,
                                 _MM_HINT_T0);////////////
                    if (massVisited[tnum] != currentV) {

                        massVisited[tnum] = currentV;

                        char *currObj1 = (getDataByInternalId(tnum));
                        dist_t dist = fstdistfunc_(datapoint, currObj1, dist_func_param_) / elementNorms[tnum];
                        dist_calc++;
                        if (topResults.top().first > dist || topResults.size() < ef) {
                            candidateSet.emplace(-dist, tnum);
                            _mm_prefetch(data_level0_memory_ + candidateSet.top().second * size_data_per_element_ +
                                         offsetLevel0_,///////////
                                         _MM_HINT_T0);////////////////////////

                            topResults.emplace(dist, tnum);

                            if (topResults.size() > ef) {
                                topResults.pop();
                            }
                            lowerBound = topResults.top().first;
                        }
                    }
                }
            }

            visitedlistpool->releaseVisitedList(vl);
            return topResults;
        }

        void SaveIndex(const std::string &location) {

            std::cout << "Saving index to " << location.c_str() << "\n";
            std::ofstream output(location, std::ios::binary);
            if (!output.is_open()) {
                std::cerr << "Open file error" << std::endl;
                exit(-1);
            }

            writeBinaryPOD(output, offsetLevel0_);
            writeBinaryPOD(output, maxelements_);
            writeBinaryPOD(output, cur_element_count);
            writeBinaryPOD(output, size_data_per_element_);
            writeBinaryPOD(output, offset_label_);
            writeBinaryPOD(output, offsetData_);
            writeBinaryPOD(output, maxlevel_);
            writeBinaryPOD(output, enterpoint_node);
            writeBinaryPOD(output, maxM_);

            writeBinaryPOD(output, maxM0_);
            writeBinaryPOD(output, M_);
            writeBinaryPOD(output, mult_);
            writeBinaryPOD(output, alpha_);
            writeBinaryPOD(output, efConstruction_);

            output.write(data_level0_memory_, maxelements_ * size_data_per_element_);
            output.write((char *) elementNorms.data(), elementNorms.size() * sizeof(float));

            for (size_t i = 0; i < maxelements_; i++) {
                unsigned int linkListSize = elementLevels[i] > 0 ? size_links_per_element_ * elementLevels[i] : 0;
                writeBinaryPOD(output, linkListSize);
                if (linkListSize)
                    output.write(linkLists_[i], linkListSize);
            }
            output.close();
        }

        void LoadIndex(const std::string &location, SpaceInterface <dist_t> *s) {

            //cout << "Loading index from " << location;
            std::ifstream input(location, std::ios::binary);
            if (!input.is_open()) {
                std::cerr << "Open file error" << std::endl;
                exit(-1);
            }

            readBinaryPOD(input, offsetLevel0_);
            readBinaryPOD(input, maxelements_);
            readBinaryPOD(input, cur_element_count);
            readBinaryPOD(input, size_data_per_element_);
            readBinaryPOD(input, offset_label_);
            readBinaryPOD(input, offsetData_);
            readBinaryPOD(input, maxlevel_);
            readBinaryPOD(input, enterpoint_node);

            readBinaryPOD(input, maxM_);
            readBinaryPOD(input, maxM0_);
            readBinaryPOD(input, M_);
            readBinaryPOD(input, mult_);
            readBinaryPOD(input, alpha_);
            readBinaryPOD(input, efConstruction_);
            printf("efConstructon_ %d, maxelements_ %d\n", efConstruction_, maxelements_);


            data_size_ = s->get_data_size();
            fstdistfunc_ = s->get_dist_func();
            dist_func_param_ = s->get_dist_func_param();

            data_level0_memory_ = (char *) malloc(maxelements_ * size_data_per_element_);
            input.read(data_level0_memory_, maxelements_ * size_data_per_element_);

            elementNorms.resize(maxelements_);
            input.read((char *) elementNorms.data(), maxelements_ * sizeof(float));


            size_links_per_element_ = maxM_ * sizeof(tableint) + sizeof(linklistsizeint);

            visitedlistpool = new VisitedListPool(1, maxelements_);


            linkLists_ = (char **) malloc(sizeof(void *) * maxelements_);
            elementLevels = std::vector<int>(maxelements_);
            revSize_ = 1.0 / mult_;
            ef_ = 10;
            for (size_t i = 0; i < maxelements_; i++) {
                unsigned int linkListSize;
                readBinaryPOD(input, linkListSize);
                if (linkListSize == 0) {
                    elementLevels[i] = 0;

                    linkLists_[i] = nullptr;
                } else {
                    elementLevels[i] = linkListSize / size_links_per_element_;
                    linkLists_[i] = (char *) malloc(linkListSize);
                    input.read(linkLists_[i], linkListSize);
                }
            }


            input.close();
            return;
        }
    };

}
